package com.wenyl.graph;

import lombok.Data;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author Swimming Dragon
 * @description: 图的邻接矩阵存储，这里以无向图为示例，无向图时双边关系所以是一个对称矩阵，
 * 如果有权值的话，可以将数组的值赋值为权值，这里默认没有权值，有关系设置为1，没关系设置为0
 * @date 2024年10月18日 13:39
 */
@Data
public class AdjacencyMatrix {
    // 邻接矩阵
    private final int[][] adjMatrix;
    // 顶点数量
    private int vertices;

    public AdjacencyMatrix(int vertices){
        this.vertices = vertices;
        adjMatrix = new int[vertices][vertices];
    }

    /**
     * 连接两个顶点
     * @param source 源顶点
     * @param destination 目的顶点
     */
    public void addEdge(int source,int destination){

        int sourceIndex = source - 1;
        int destinationIndex = destination - 1;
        if(!isLegal(sourceIndex,destinationIndex)){
            System.out.println("顶点不存在");
            return;
        }
        // 有向图设置单边即可，有权值的话，将1设置为权值，这里仅作无向图
        adjMatrix[sourceIndex][destinationIndex] = 1;
        adjMatrix[destinationIndex][sourceIndex] = 1;
    }
    public void printGraph() {
        for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++) {
                System.out.print(adjMatrix[i][j] + " ");
            }
            System.out.println();
        }
    }
    public boolean isLegal(int source,int destination){
        return source >=0 && source <vertices && destination >=0 && destination <vertices;
    }

    /**
     * 从指定节点开始做广度优先遍历
     * @param startVertex 起始节点
     */
    public void bfs(int startVertex){
        System.out.println("广度优先遍历结果: ");
        int startVertexIndex = startVertex-1;
        boolean[] visited = new boolean[vertices];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(startVertexIndex);
        visited[startVertexIndex] = true;
        while(!queue.isEmpty()){
            int currentVertex = queue.poll();
            System.out.print((currentVertex+1) + " ");
            // 把没有遍历过的并且与这个节点连接的节点放入到队列
            for(int i=0;i<vertices;i++){
                if(adjMatrix[currentVertex][i] == 1 && !visited[i]){
                    queue.add(i);
                    visited[i] = true;
                }
            }
        }
        System.out.println();
    }
    /**
     * 从指定节点开始做深度优先遍历
     * @param startVertex 起始节点
     */
    public void dfs(int startVertex){
        System.out.println("深度优先遍历结果: ");
        int startVertexIndex = startVertex-1;
        boolean[] visited = new boolean[vertices];
        Stack<Integer> stack = new Stack<>();
        visited[startVertexIndex] = true;
        stack.add(startVertexIndex);
        while(!stack.isEmpty()){
            int currentVertex = stack.pop();
            System.out.print((currentVertex+1) + " ");
            for(int i=0;i<vertices;i++){
                if(adjMatrix[currentVertex][i] == 1 && !visited[i]){
                    stack.add(i);
                    visited[i] = true;
                }
            }
        }
        System.out.println();
    }

}
